#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

struct Node{
	int val;
	struct Node * left;
	struct Node * right;
};

void split(string str, const char splitChar, vector<string> & res){
	istringstream iss(str);// 输入流
	string token; // 接受缓冲区
	while(getline(iss, token, splitChar)){
		res.push_back(token);
	}
}

int getHeight(struct Node * head){
	if(head){
		return max(getHeight(head->left), getHeight(head->right)) + 1;
	}
	return 0;
}

void serializeMidTree(struct Node * head, string & res, int height){
	if(head != nullptr || height > 0){
		height--;
		string val;
		if(head != nullptr){
			serializeMidTree(head->left, res, height);
			val = to_string(head->val);
		} else {
			serializeMidTree(nullptr, res, height);
			val = "null";
		}
		res += val;
		res += ',';
		if(head != nullptr){
			serializeMidTree(head->right, res, height);
		} else {
			serializeMidTree(nullptr, res, height);
		}
	}
}

// 将二叉树插入vector当中 序列化
void serialize(struct Node * head, string & res){
	int height = getHeight(head);
	serializeMidTree(head, res, height);
}


// 7,3,8,1,9,4,10, 0, 11,5,12,2,13,6,14, 中序
void combine(Node * head, vector<string> leftV, vector<string> rightV){
	int len = leftV.size();
	int mid = len/2;
	Node * left = new Node;
	Node * right = new Node;
	
	// 这四个设置为空的步骤非常重要，否则会有野指针问题
	left->left = nullptr;
	left->right = nullptr;
	right->left = nullptr;
	right->right = nullptr;

	// cout << leftV[mid] << endl;
	if(leftV[mid] != "null"){
		left->val = stoi(leftV[mid]);
		head->left = left;
	} 
	if(rightV[mid] != "null"){
		right->val = stoi(rightV[mid]);
		head->right = right;
	}
	// cout << "left:" << left->val << ",right:" << right->val << ",len:" << len << endl;
	
	if(len == 1){
		 
		return;
	}
	if(leftV[mid] != "null"){
		combine(left, {leftV.begin(), leftV.begin() + mid}, {leftV.begin() + mid + 1, leftV.end()});
	}
	if(rightV[mid] != "null"){
		combine(right, {rightV.begin(), rightV.begin() + mid}, {rightV.begin() + mid + 1, rightV.end()});
	}
}

// 0, 1, 3,7,8, 4,9,10, 2, 5,11,12, 6,13,14, 先序遍历反解 反序列化， 确定左子树顶节点
// 7, 3, 8, 1, 9,4,10, 0, 11, 5 ,12, 2 ,13,6,14, 中序  确定左子树的范围
struct Node * deserialize(string data){
	// 1.将字符串填入到栈中
	// 2.一次取得栈顶元素填入到二叉树中
	// vector<string> front, mid; // 前序排列 中序排列
	// int len = data.size();
	// front.assign(data.begin(), data.begin() + len/2);
	// mid.assign(data.begin() + len/2, data.end());
	Node * head = new Node;
	vector<string> midV;
	split(data, ',', midV);
	for(auto i : midV){
		cout << i << ",";
	}
	cout << endl;
	

	int len = midV.size();
	int mid = len/2;
	vector<string> leftV;
	vector<string> rightV;
	head->val = stoi(midV[mid]);

	leftV.assign(midV.begin(), midV.begin() + mid);
	rightV.assign(midV.begin() + mid +1, midV.end());

	combine(head, leftV, rightV);
	return head;
}

// 1.先序递归遍历
void showPrefix(struct Node * head){
	if(head){
		cout << head->val << ",";
		showPrefix(head->left);
		showPrefix(head->right);
	}
}

// 1.先序非递归遍历
/*
思路：
1.定义一个栈用于存放右节点的数据，
2.每次遍历均打印该左节点的值。并查看是否有右节点，如果有，则【压栈】。
3.当遍历到左节点到最后一个的时候，则取【栈顶】的数据【右节点】，并打印之。
4.同样的方式再访问该右节点的所有左子节点。并查看是否有右节点，如果有，则【压栈】。 重复2,3步骤
5.当当前栈为空的时候，代表所有节点遍历结束
*/
void showPrefixNo(struct Node * head){
	// 1.先定义一个栈
	stack<Node *> nodeList;
	int top = 1;
	nodeList.push(head);
	while(top > 0){
		Node * index = nodeList.top();
		nodeList.pop();
		top--;
		while(index){
			cout << index->val << ",";
			// Node * left = head->left;
			if(index->right){
				nodeList.push(index->right);
				top++;
			}
			index = index->left;
		}
	}
}

// 2.中序递归遍历
void showMid(struct Node * head){
	if(head){
		showMid(head->left);
		cout << head->val << ",";
		showMid(head->right);
	}
}

// 3.中序非递归遍历
/*
思路：
1.定义一个栈，用于存储节点信息
2.先将所有的左节点压栈，直到最后一个节点【此时输出节点信息】
3.出栈，并打印信息
4.出栈的同时检查是否有右节点，如果有，则继续将该右节点信息压栈，重复2,3
5.栈空则结束
*/
void showMidNo(struct Node * head){
	stack<Node *> nodeList;
	int top = 0;
	// nodeList.push(head);
	Node * index = head;
	while(top >= 0){
		if(index){
			nodeList.push(index);
			index = index->left;
			top++;
		}else{
			index = nodeList.top();
			cout << index->val << ","; // 打印自己
			nodeList.pop();
			top--;
			if(top > 0){
				Node* topItem = nodeList.top();		
				cout << topItem->val << ","; // 打印父节点
				nodeList.pop();
				top--;
				index = topItem->right;
			}else{
				break;
			}
		}
	}
}

// 3.后序递归遍历
void showAfter(struct Node * head){
	if(head){
		showAfter(head->left);
		showAfter(head->right);
		cout << head->val << ",";
	}
}

// 3.后序非递归遍历
void showAfterNo(struct Node * head){
	stack<Node *> nodeList;
	int top = 0;
	Node * index = head;
	while(top >= 0){
		if(index){
			nodeList.push(index);
			index = index->left;
			top++;
		} else {
			Node* leftItem = nodeList.top(); // 最后一个左节点
			nodeList.pop();
			top--;
			cout << leftItem->val << ","; // 输出最左最节点
			
			Node * topItem = nodeList.top();
			Node * rightItem = topItem->right;
			if(rightItem->left){
				index = rightItem;
			}else{
				cout << rightItem->val << ","; // 输出右节点
				cout << topItem->val << ","; // 输出中间节点
				nodeList.pop();
				top--;
				
			}
		}
	}
}

/*
					  head0	
			n1			        n2
	    n3       n4         n5        n6
	 n7   n8   n9  n10   n11 n12   n13  n14


*/

struct Node * init(){
	struct Node * head = new Node;
	head->val = 0;
	head->left = nullptr;
	head->right = nullptr;
	
	struct Node * n1 = new Node;
	n1->val = 1;
	n1->left = nullptr;
	n1->right = nullptr;
	head->left = n1;
	
	struct Node * n2 = new Node;
	n2->val = 2;
	n2->left = nullptr;
	n2->right = nullptr;
	head->right = n2;
	
	// struct Node * n3 = new Node;
	// n3->val = 3;
	// n3->left = nullptr;
	// n3->right = nullptr;
	// n1->left = n3;
	
	// struct Node * n4 = new Node;
	// n4->val = 4;
	// n4->left = nullptr;
	// n4->right = nullptr;
	// n1->right = n4;
	
	struct Node * n5 = new Node;
	n5->val = 5;
	n5->left = nullptr;
	n5->right = nullptr;
	n2->left = n5;
	
	struct Node * n6 = new Node;
	n6->val = 6;
	n6->left = nullptr;
	n6->right = nullptr;
	n2->right = n6;
	
	// struct Node * n7 = new Node;
	// n7->val = 7;
	// n7->left = nullptr;
	// n7->right = nullptr;
	// n3->left = n7;
	
	// struct Node * n8 = new Node;
	// n8->val = 8;
	// n8->left = nullptr;
	// n8->right = nullptr;
	// n3->right = n8;
	
	// struct Node * n9 = new Node;
	// n9->val = 9;
	// n9->left = nullptr;
	// n9->right = nullptr;
	// n4->left = n9;
	
	// struct Node * n10 = new Node;
	// n10->val = 10;
	// n10->left = nullptr;
	// n10->right = nullptr;
	// n4->right = n10;
	
	struct Node * n11 = new Node;
	n11->val = 11;
	n11->left = nullptr;
	n11->right = nullptr;
	n5->left = n11;
	
	struct Node * n12 = new Node;
	n12->val = 12;
	n12->left = nullptr;
	n12->right = nullptr;
	n5->right = n12;
	
	struct Node * n13 = new Node;
	n13->val = 13;
	n13->left = nullptr;
	n13->right = nullptr;
	n6->left = n13;
	
	struct Node * n14 = new Node;
	n14->val = 14;
	n14->left = nullptr;
	n14->right = nullptr;
	n6->right = n14;
	
	return head;
}

int main(){
	
	// string midStr ="7,3,8,1,9,4,10,0,11,5,12,2,13,6,14"; // 中序排列字符串
	// struct Node * head = deserialize(midStr);
	// // cout << head->left->left->left->left->val <<endl;
	// showMid(head);
	// return 0;

	// string a = "123";
	// int b = stoi(a);
	// cout << b << endl;
	// return 0;
	
	struct Node * head = init();
	cout << "before:" ;
	showMid(head);
	cout << endl;
	string res;
	serialize(head, res);
	cout << "res:" << res << endl;

	cout << "after:";
	struct Node * newHead = deserialize(res);
	showMid(newHead);
	return 0;
	
}